package com.roy.galaxy.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * @author gang.wang1903@xiaobao100.cn
 * @Date: 2019-10-17 09:22
 * 考察数组的计算：空间复杂度与时间复杂度
 */
public class 两数之和 {


    /**
     * 实践复杂度O(n^2) 空间复杂度O(1)
     * @param target
     * @param nums
     * @return
     */
    public int[] getSumIndex(int target,int[] nums){

        for(int i = 0 ; i <  nums.length-1 ; i++){

            for(int j = i ; j < nums.length-1 ; j ++ ){
                if((nums[i] + nums[j+1]) == target){
                    return new int[]{i,j+1};
                }
            }
        }

        return null;
    }

    /**
     * 两数之和优化
     * @param target
     * @param nums
     * @return
     * 时间复杂度O(n),空间复杂度O(n)
     */
    public int[] getSumIndex2(int target,int[] nums) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[]{i, map.get(complement)};
            }
        }
        return null;
    }

    public static void main(String[] args) {
       int[] result = new 两数之和().getSumIndex(6,new int[]{3,2,4});
       System.out.print(result[0]+"---"+result[1]);
    }
}
